/*************************************************************************
 * File Name:    Longest_Consecutive_Sequence.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: Sun 27 Oct 2013 04:44:15 PM CST
 * 
 * Description:  
 |------------------------------------------------------------------------
 | Problem: Longest Consecutive Sequence
 |
 | Given an unsorted array of integers, find the length of the longest
 | consecutive elements sequence.
 |
 | For example,
 | Given [100, 4, 200, 1, 3, 2],
 | The longest consecutive elements sequence is [1, 2, 3, 4].
 | Return its length: 4.
 |
 | Your algorithm should run in O(n) complexity.
 |------------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <iomanip>

using namespace std;

class Solution {
/*
 * solution: First create an hash map, which indicate whether an number 
 * exists. Then we can use dfs to search an number, extends it to its 
 * two sides neighbors, set it visited, util couldn't extends.
 */
public:
    int longestConsecutive(vector<int> &num) {
        int ans = 1;
        set<int> s;
        for (size_t i = 0; i < num.size(); ++i) {
            s.insert(num[i]);
        }
        vector<int> sorted_num(s.begin(), s.end());
        size_t pre = 0;
        for (size_t i = 1; i < sorted_num.size(); ++i) {
            if (sorted_num[i] != sorted_num[i - 1] + 1) {
                if (ans < i - pre) ans = i - pre;
                pre = i;
            }
            if (i + 1 == sorted_num.size()) {
                if (ans < i - pre + 1) ans = i - pre + 1;
            }
        }
        return ans;
    }
};

int
main(int argc, char *argv[])
{

    return 0;
}
